import java.util.ArrayList;
import java.util.List;

public class Test {
}
class Solution {
    public long minimumFuelCost(int[][] roads, int seats) {
        int n = roads.length+1;
        List<Integer>[] list = new ArrayList[n];
        for(int i=0; i<n; i++)
            list[i] = new ArrayList<>();
        for(int[] x : roads){
            list[x[0]].add(x[1]);
            list[x[1]].add(x[0]);
        }
        dfs(0,-1,list,seats);
        return ans;
    }
    private long ans;
    int dfs(int i, int parent, List<Integer>[] list, int seats){
        int size = 1;
        for(int x : list[i]){
            if(x != parent){
                size += dfs(x, i, list, seats);
            }
        }
        if(i > 0){
            ans += (size-1)/seats + 1;
        }
        return size;
    }
}

